https://leetcode.com/problems/jewels-and-stones/
You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.
The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".
Example 1:
Input: J = "aA", S = "aAAbbbb"
Output: 3
Example 2:
Input: J = "z", S = "ZZ"
Output: 0
Note:
S and J will consist of letters and have length at most 50.
The characters in J are distinct.
public class Solution {
public int NumJewelsInStones(string J, string S) {
int cnt = 0;
for (int i = 0; i < S.Length; i++)
{
if (J.IndexOf(S[i]) > -1)
{
cnt++;
}
}
return cnt;
}
}
Runtime: 76 ms, faster than 83.98% of C# online submissions.
Memory Usage: 22.4 MB, less than 7.14% of C# online submissions.
Time Complexity: O(n)
Space Complextiy: O(1)
這題沒有很難，你可以用一個 for 迴圈就可以判斷每個 stone 是不是 jewels。
indexOf 去 判斷這顆 stone 是不是屬於 jewels
顆數 (cnt)
以上就是這次 LeetCode 刷題的分享啦！
如果其它人有更棒的想法及意見，請留言或寄信(t4730@yahoo.com.tw) 給我。
那我們就下回見囉 
IndexOf 應該會一個一個的遍尋，才能找到是在哪個 index，這樣效能應該不好
先 for loop J 將出現過的字母存入到 Map，後續再用 Map 來找應該會更好
後來看了有更好的解法是，因為 A-Z a-z 範圍大概在 65 - 122
所以宣告 int[] isSeen = new int[123]; 若有出現過則 isSeen[i] = 1;
直接以 array index 查找，也省掉轉型的時間
public int numJewelsInStones(String J, String S) {
int[] isSeen = new int[123]; // z is 122
for (int i = 0, length = J.length(); i < length; i++)
isSeen[J.charAt(i)] = 1;
int cnt = 0;
for (int i = 0, length = S.length(); i < length; i++) {
if (isSeen[S.charAt(i)] == 1)
cnt++;
}
return cnt;
}
iThome鐵人賽
看影片追技術